package top.retain;

import java.util.Arrays;
import java.util.Random;

/**
 * @author ivorfan
 * @date 2021/8/3 14:35
 */
public class Sort {


    public static void main(String[] args) {
        Sort s = new Sort();
        int[] nums = s.generateArr(6);
//        s.bubbleSort(nums);
//        s.selectSort(nums);
//        s.insertSort(nums);
//        s.shellSort(nums);
        s.mergeSort(nums,0, nums.length - 1);
//        s.countingSort(nums);
        s.printArr(nums);

    }

    Random r = new Random();
    public int[] generateArr(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = r.nextInt(100);
        }
        return arr;
    }

    public void printArr(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void bubbleSort(int[] nums) {
        // j < nums - 1 -i : -i表示倒数前i个已经排好了，不需要遍历。
        for (int i = 0; i < nums.length; i ++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    /**
     * 选择排序：每轮将最小的数排到最前面
     */
    public void selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 默认第一个为最小值
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

    /**
     * 插入排序，未完成
     */
    public void insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            // 后一个数比前一个数大，需要排序
            if (nums[i] < nums[i - 1]) {
                int temp = nums[i];
                for (int j = i; j > 0; j--) {
                    // 从i开始往前。如果比前一个小则交换
                    if (nums[j] < nums[j - 1]) {
                        // 大的到后面
                        nums[j] = nums[j - 1];
                        // 小到到前面
                        nums[j - 1] = temp;
                    }else {
                      break;
                    }
                }
            }
            printArr(nums);
        }
    }


    public void shellSort(int[] nums) {
        printArr(nums);
        int j;
        for (int gap = nums.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                int temp = nums[i];

                for (j = i; j >= gap && temp < nums[j - gap] ; j -=gap) {
                    nums[j] = nums[j - gap];
                }
                nums[j] = temp;
            }
            printArr(nums);
        }
    }


    public void mergeSort(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        if (left < right) {
            // 二分进入左边
            mergeSort(nums,left, mid);
            // 二分进入右边
            mergeSort(nums, mid + 1, right);
            // 合并两个数组
            merge(nums, left, mid, right);
            printArr(nums);
        }

    }

    /**
     * 左右归并
     */
    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        // 左指针
        int i =left;
        // 右指针
        int j = mid + 1;
        int k = 0;
        // 把较小到数移动到新数组
        while (i <= mid && j <= right) {
            // 这里类似两个链表合并，合并两个有序数组
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }
        // 把左边剩余到数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 把右边剩余到数移入数组
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        // 数组中到数覆盖nums
        for (int l = 0; l < temp.length; l++) {
            nums[left + l] = temp[l];
        }
    }

    /**
     * 计数排序
     */
    public void countingSort(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] bucket = new int[max + 1];
        for (int num : nums) {
            bucket[num]++;
        }
        int sortedIndex = 0;
        for (int i = 0; i < max + 1; i++) {
            while (bucket[i] > 0) {
                nums[sortedIndex++] = i;
                bucket[i]--;
            }
        }
    }
}
